package main.Q1101_1200;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class Q1141_1150 {
    public static void main(String[] args) {
        System.out.println("Question1141：");
        System.out.println("Question1142：");
        System.out.println("Question1143：最长公共子序列");
        System.out.println("Question1144：");
        System.out.println("Question1145：");
        System.out.println("Question1146：快照数组");
        System.out.println("Question1147：");
        System.out.println("Question1148：");
        System.out.println("Question1149：");
        System.out.println("Question1150：");
    }
}

class Question1143{
    public static int longestCommonSubsequence(String text1, String text2) {
        int length1=text1.length(),length2=text2.length(),max=0;
        char[] str1=text1.toCharArray(),str2=text2.toCharArray();
        int[][] dp=new int[length1+1][length2+1];
        for (int i=0;i<length1+1;i++){//添加了一个空串，下标整体+1
            for (int j=0;j<length2+1;j++){
                if (i==0||j==0) dp[i][j]=0;//任何一个子串与空串的最长子序列长度均为0
                else {
                    if (str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1]+1;//二者子串结尾字符相同时那么之前最长子序列长度+1
                    else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);//二者子串结尾字符不同时，判断指向最大值
                }
                max=Math.max(max,dp[i][j]);
            }
        }
        return max;
    }
}

class Question1146{
    private Map<Integer, TreeMap<Integer, Integer>> map;
    private int snap_id;

    public Question1146(int length) {
        map = new HashMap<>();
        snap_id = 0;
        for (int i = 0; i < length; i++) {
            TreeMap<Integer, Integer> tree = new TreeMap<>();
            tree.put(0, 0);
            map.put(i, tree);
        }
    }

    public void set(int index, int val) {
        TreeMap<Integer, Integer> tree = map.get(index);
        tree.put(snap_id, val);
    }

    public int snap() {
        return snap_id++;
    }

    public int get(int index, int snap_id) {
        TreeMap<Integer, Integer> tree = map.get(index);
        return tree.floorEntry(snap_id).getValue();
    }
}